package mo.offer_special;

public class L096 {

    public boolean isInterleave(String s1, String s2, String s3) {
        int i1 = s1.length(), i2 = s2.length(), i3 = s3.length();
        if (i1 + i2 != i3) {
            return false;
        }
        boolean[][] dp = new boolean[i1 + 1][i2 + 1];
        dp[0][0] = true;
        for (int i = 0; i <= i1; i++) {
            for (int j = 0; j <= i2; j++) {
                int p = i + j - 1;
                if (i > 0) {
                    dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
                }
                if (j > 0) {
                    dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }
        return dp[i1][i2];
    }

    public static void main(String[] args) {
        L096 test = new L096();
        System.out.println(test.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
    }

}
